package com.hy.greedy;

import com.hy.treeNode.TreeNode;

public class MonitoringBinaryTree {


    /**
     * 968.监控二叉树
     * 力扣题目链接
     *
     * 给定一个二叉树，我们在树的节点上安装摄像头。
     *
     * 节点上的每个摄影头都可以监视其父对象、自身及其直接子对象。
     *
     * 计算监控树的所有节点所需的最小摄像头数量。
     *
     * 思路
     * 这道题目首先要想，如何放置，才能让摄像头最小的呢？
     *
     * 从题目中示例，其实可以得到启发，我们发现题目示例中的摄像头都没有放在叶子节点上！
     *
     * 此时这道题目还有两个难点：
     * 二叉树的遍历
     * 如何隔两个节点放一个摄像头
     * 确定遍历顺序
     * 在二叉树中如何从低向上推导呢？
     *
     * 可以使用后序遍历也就是左右中的顺序，这样就可以在回溯的过程中从下到上进行推导了。
     *
     * 后序遍历代码如下：
     *
     * int traversal(TreeNode* cur) {
     *
     *     // 空节点，该节点有覆盖
     *     if (终止条件) return ;
     *
     *     int left = traversal(cur->left);    // 左
     *     int right = traversal(cur->right);  // 右
     *
     *     逻辑处理                            // 中
     *     return ;
     * }
     *
     * 如何隔两个节点放一个摄像头
     * 此时需要状态转移的公式，大家不要和动态的状态转移公式混到一起，本题状态转移没有择优的过程，就是单纯的状态转移！
     *
     * 来看看这个状态应该如何转移，先来看看每个节点可能有几种状态：
     *
     * 有如下三种：
     *
     * 该节点无覆盖
     * 本节点有摄像头
     * 本节点有覆盖
     * 我们分别有三个数字来表示：
     *
     * 0：该节点无覆盖
     * 1：本节点有摄像头
     * 2：本节点有覆盖
     *
     */
    int res = 0;
    public int minCameraCover(TreeNode root){
        if (minCame(root) == 0){
            res ++;
        }
        return res;
    }
    /**
     节点的状态值：
     0 表示无覆盖
     1 表示 有摄像头
     2 表示有覆盖
     后序遍历，根据左右节点的情况,来判读 自己的状态
     */
    public int minCame(TreeNode root){
        if (root == null){
            // 空节点默认为 有覆盖状态，避免在叶子节点上放摄像头
            return 2;
        }
        int left = minCame(root.left);
        int right = minCame(root.right);
        // 如果左右节点都覆盖了的话, 那么本节点的状态就应该是无覆盖,没有摄像头
        if (left == 2 && right == 2){
            return 0;
        }else if(left  == 0 || right == 0){
            // 左右节点都是无覆盖状态,那 根节点此时应该放一个摄像头
            // (0,0) (0,1) (0,2) (1,0) (2,0)
            // 状态值为 1 摄像头数 ++;
            res ++;
            return 1;
        }else {
            // 左右节点的 状态为 (1,1) (1,2) (2,1) 也就是左右节点至少存在 1个摄像头，
            // 那么本节点就是处于被覆盖状态
            return 2;
        }
    }
    public static void main(String[] args) {
        MonitoringBinaryTree monitoringBinaryTree = new MonitoringBinaryTree();

        TreeNode leftNode1 = new TreeNode(1, null, null);
        TreeNode rightNode1 = new TreeNode(2, null, null);

        TreeNode leftNode2 = new TreeNode(6, null, null);
        TreeNode rightNode2 = new TreeNode(8, null, null);

        TreeNode leftNode = new TreeNode(4, leftNode1, rightNode1);
        TreeNode rightNode = new TreeNode(7, leftNode2, rightNode2);

        TreeNode root = new TreeNode(5, leftNode, rightNode);

        System.out.println("res: "+monitoringBinaryTree.minCameraCover(root));

    }
}
